function asset(value, msg) {
    if (!value) {
        throw new Error(`error:${msg}`);
    }
}

let updates = 0;
let header = null;

class DancingNode {
    constructor(c) {
        this.L = this.R = this.U = this.D = this;
        this.C = c;
    }

    // hooks node n1 `below` current node
    hookDown(n1) {
        asset(this.C === n1.C);
        n1.D = this.D;
        n1.D.U = n1;
        n1.U = this;
        this.D = n1;
        return n1;
    }

    // hooke a node n1 to the right of `this` node
    hookRight(n1) {
        n1.R = this.R;
        n1.R.L = n1;
        n1.L = this;
        this.R = n1;
        return n1;
    }

    unlinkLR() {
        this.L.R = this.R;
        this.R.L = this.L;
        updates++;
    }

    relinkLR() {
        this.L.R = this.R.L = this;
        updates++;
    }

    unlinkUD() {
        this.U.D = this.D;
        this.D.U = this.U;
        updates++;
    }

    relinkUD() {
        this.U.D = this.D.U = this;
        updates++;
    }
}

class ColumnNode extends DancingNode {
    constructor(name) {
        super();
        this.size = 0;// number of ones in current column
        this.name = name;
        this.C = this;
    }

    cover() {
        this.unlinkLR();
        for (let i = this.D; i != this; i = i.D) {
            for (let j = i.R; j != i; j = j.R) {
                j.unlinkUD();
                j.C.size--;
            }
        }
        header.size--; // not part of original
    }

    uncover() {
        for (let i = this.U; i != this; i = i.U) {
            for (let j = i.L; j != i; j = j.L) {
                j.C.size++;
                j.relinkUD();
            }
        }
        this.relinkLR();
        header.size++; // not part of original
    }
}

class DLX {
    constructor(map) {
        this.header = header = this.mkDLXBoard(map);
        this.runSolver();
    }

    mkDLXBoard(map) {
        let cols = map[0].length;
        let rows = map.length;

        let headerNode = new ColumnNode('header');
        let columnNodes = [];
        for (let i = 0; i < cols; ++i) {
            let colNode = new ColumnNode(i.toString());
            columnNodes.push(colNode);
            headerNode = headerNode.hookRight(colNode);
        }

        headerNode = headerNode.R.C;

        for (let i = 0; i < rows; i++) {
            let prev = null;
            for (let j = 0; j < cols; j++) {
                if (map[i][j] > 0) {
                    let col = columnNodes[j];
                    let newNode = new DancingNode(col);
                    if (prev == null) {
                        prev = newNode;
                    }
                    col.U.hookDown(newNode);
                    prev = prev.hookRight(newNode);
                    col.size++;
                }
            }
        }

        headerNode.size = cols;

        return headerNode;
    }

    runSolver() {
        this.solutions = 0;
        this.handler = new DefaultHandler();
        updates = 0;
        this.answer = [];
        this.search(0);
        this.showInfo();
    }

    showInfo(){
        console.log("Number of updates: " + updates);
    }

    selectColumnNodeHeuristic() {
        let min = Number.MAX_VALUE;
        let ret = null;
        for (let c = this.header.R; c != this.header; c = c.R) {
            if (c.size < min) {
                min = c.size;
                ret = c;
            }
        }
        return ret;
    }

    selectColumnNodeNaive(){
        return  this.header.R;
    }

    search(k) {
        if (this.header.R === this.header) { // all the columns removed
            console.log("-----------------------------------------");
            console.log("Solution #" + this.solutions + "\n");
            this.handler.handleSolution(this.answer);
            console.log("-----------------------------------------");
            this.solutions++;
        } else {
            let c = this.selectColumnNodeNaive();
            c.cover();

            for (let r = c.D; r != c; r = r.D) {
                this.answer.push(r);

                for (let j = r.R; j != r; j = j.R) {
                    j.C.cover();
                }

                this.search(k + 1);

                r = this.answer.pop();
                c = r.C;

                for (let j = r.L; j != r; j = j.L) {
                    j.C.uncover();
                }
            }
            c.uncover();
        }
    }
}

class DefaultHandler {
    handleSolution(answer) {

        answer.forEach((n)=>{
            let ret = "";
            ret += n.C.name + " ";
            let tmp = n.R;
            while (tmp != n) {
                ret += tmp.C.name + " ";
                tmp = tmp.R;
            }
            console.log(ret);
        });
    }
}


let map = [
    [0,0,1,0,1,1,0], // 1
    [1,0,0,1,0,0,1],
    [0,1,1,0,0,1,0],
    [1,0,0,1,0,0,0], // 4
    [0,1,0,0,0,0,1], // 5
    [0,0,0,1,1,0,1],
];
let dlx = new DLX(map);
